网络链接的预测：概念与前沿是一篇关于链路预测的综述性文章。
什么是链路预测
根据已有的网络结构预测存在但未被观察到、或者未来可能出现的链路。
链路预测的应用场景
- 指导生物实验提高实验成功率
- 社交网络进行朋友推荐
- 电子商务进行商品推荐
- 对信息不完全的网络进行重构
- 基于节点相似性的社团划分
链路预测的测试集选取方法
已知连边分两部分：训练集、测试集。已知连边中随机选取一定比例的连边构成测试集。
- 网络是含时的，按时间顺序将最近产生的连边构成测试集
- 考察小度节点产生连边的预测时，选择小度节点的连边组成测试集
衡量链路预测算法精确度的指标
AUC：Area Under ROC Curve，即ROC曲线下的面积
理论上：测试集中随机选取一条边的分数值（分数值由预测算法给出，值越高表示出现的概率越高）比随机选择一条不存在的边的分数值高的概率。
实际中：每次从测试集和不存在边的集合中各随机选一条边a、b，二者分数值为v(a)、v(b)。若v(a)>v(b)，AUC加1；若v(a)=v(b)，AUC加0.5。独立比较多次所得平均值即为AUC。
链路预测的方法
基于节点属性相似性
- 在能获得节点的标签时比较标签相似性，如年龄、性别、兴趣等。
- 在标签并非显而易见时，分析文本相似性，如用户收藏或发表的问题、参与的话题等。
基于网络结构相似性
不能获得节点的标签时，根据网络结构计算节点相似性。此方法有以下几种相似性指标。
- 优先连接。 点x度为v(x)，点y度为v(y)，则x、y产生新边的概率p ∝ v(x)*v(y)。
- 共同邻居。 点x、y产生新边的概率p ∝ xy共同邻居数。
- AA指标。 当认为不同的共同邻居的影响力不同时，给共同邻居加上权重。若共同邻居m点度为v(m)，则m权重M为节点的度的对数的倒数，则AA指标为所有共同邻居的权重之和。
- LHH2指标。 两节点的邻居节点相似，则这两个节点也相似。
基于似然分析
一个N个节点的网络可用一个包含N个叶子节点的数表示，这N个叶子节点由N-1个非叶子节点连接起来，依次往上。每个非叶子节点有一个概率值，则两个节点连接的概率为它们最近共同祖先节点的概率值。
基于机器学习
- 基于特征分类方法。 哈桑等人提取合著网络中科学家研究领域的关键词作为特征，用监督学习中常见的分类算法对缺失的连边进行了较为准确的预测，如决策树、k邻近法、多层感知机、支持向量机，其中支持向量机效果最佳。文中介绍不清。
- 基于概率图模型方法。 使用图模型来表达节点之间的连边概率。文中介绍不清。
- 基于矩阵分解方法。 此方法要学习的参数很少，但计算复杂度较高。文中介绍不清。
复杂网络上的链接预测
复杂网络复杂在网络含权、含时、多层、有向。
文献提出了有向网络链路预测的“势理论”：在一个有向子图中，任选一个节点并给定初始的势能，顺边方向的邻居的势能降低1，逆边方向的邻居的势能增加1。一条有向边的加入能够产生的含有四个节点的双风扇结构越多，则出现的概率越大。
可预测性
“结构一致性”指标可以用来衡量网络被预测的难易程度。网络一致性越强的网络，丢失的边也越容易被准确地预测出来。文中给出了计算网络结构一致性的方法，只是简单定义，介绍不清。
待发展方向
- 如何得到一个不依赖于预测算法的链路预测上界
- 如何在复杂网络中进行链路预测
- 如何在超大规模网络上有效利用多维的信息进行链路预测